差分数组：
对有 nnn 个数据的数组 a[]a[]a[] ，其差分数组 d[]d[]d[] 使得 d[]d[]d[] 的前缀和可以获得 a[]a[]a[] ,即:
ai=∑k=0idk(1)a_i=\displaystyle \sum_{k=0}^{i}d_k\tag{1} ai =k=0∑i dk (1)
由此移项，可得：
di=ai−ai−1(2)d_i=a_i-a_{i-1}\tag{2} di =ai −ai−1 (2)
则易得若将 d[i]d[i]d[i] 增加 ccc ，则在数组 a[]a[]a[] 中，数据 ai、ai+1......、ana_i、a_{i+1}......、a_nai 、ai+1 ......、an 都会增加 ccc 。
因此，若要将序列 a[]a[]a[] 中 [l,r][l,r][l,r] 之间的数都增加 ccc ，则我们需要有dl+=cd_l+=cdl +=c且dr+1−=cd_{r+1}-=cdr+1 −=c，时间复杂度为 O(1)O(1)O(1)
例题：
区间修改(集训营入口)
区间修改(非集训营入口)
STSTST表:
解决在线RMQRMQRMQ问题的工具。
步骤：
111 设Fi jF_{i\ j}Fi j 表示区间 [i,i+2j−1][i,i+2^j-1][i,i+2j−1] 区间的最值，区间长度为2j2^j2j，填表的时间复杂度为 O(nlogn)O(n\log n)O(nlogn) ，递推式为：
Fi j=max(Fi, j−1,Fi+2j−1 j−1)(3)F_{i\ j}=\max(F_{i,\ j-1},F_{i+2^{j-1}\ j-1})\tag{3} Fi j =max(Fi, j−1 ,Fi+2j−1 j−1 )(3)
分治法：
指定对于一个规模为 NNN 的问题，将其分解为 MMM 个规模较小的子问题。这些子问题互相独立(即子问题之间不包含公共的子子问题)且与原问题形式相同，递归解这些子问题，合并其解可得原问题的解。分治的核心代码主要集中在分解和合并阶段，治理极端的核心点事递归参数和递归边界。
快速排序：
问题：对一个长度为 NNN 的序列 a[N]a[N]a[N] ，将其升序排列。
方法：从序列中任取一个元素 xxx ，将所有小于等于 xxx 的元素放到 xxx 的左边，所有大于等于 xxx 的元素放到 xxx 的右边，此时 xxx 的位置必定正确，下面是使用双指针的方式解决快速排升序问题的代码：
快速排序的一次划分算法从两头交替搜索，直到指针 low\mathrm{low}low 和指针 high\mathrm{high}high 重合，因此其时间复杂度是 O(n)O(n)O(n) 。而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是每次划分所选择的中间数恰好将当前序列几乎等分，经过 log2n\log_2nlog2 n 趟划分，便可得到长度为 111 的子数组。这样，整个算法的时间复杂度为 O(nlogn)O(n\log n)O(nlogn) 。而最坏的情况是每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子数组中一个为空，另一子表的长度为原数组的长度
−1-1−1。这样，长度为 nnn 的数据表的快速排序需要经过 nnn 趟划分后的时间复杂度为 O(n2)O(n^2)O(n2)。
归并排序：
步骤如下：
1.1.1. 将给定的包含 nnn 个元素的局部数组"分割"成两个局部数组，每个数组各包含 n2\dfrac{n}{2}2n 个元素。(划分)
2.2.2. 对两个局部数组分别执行 MergeSort\mathrm{MergeSort}MergeSort 排序。(处理)
3.3.3. 通过 Merge\mathrm{Merge}Merge 将两个已排序完毕的局部数组"整合"成一个数组。(合并)
代码：
树与图：
边的数量： 对于有 nnn 个节点的树，有且只有 n−1n-1n−1 条边。
路径： 在一棵树中，一个结点和根结点的通路称为路径。在第 kkk 层的结点的路径长度为 k−1k-1k−1 (如果称根结点处在第 111 层)。一个结点的路径长度乘以该结点的权值，为结点的带权路径长度，其中权是给一个结点赋予的有意义的值。树的带权路径长度规定为所有叶子结点的带权路径长度之和。
哈夫曼树： 使得的带权路径长度最短的树称为哈夫曼树，又称为最优二叉树。哈夫曼树通常为二叉树。
哈夫曼树的构造：
对于给定带有各自权值的 nnn 个结点，构造哈夫曼树：
1.1.1. 在 nnn 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树的一个结点的左右孩子。
2.2.2. 删除使用过的两个权值，将新的权值加入到权值集合中。
3.3.3. 重复 111 和 222 ，直到无法再选出两个权值，此时这个二叉树就是哈夫曼树。
通俗点：最底下一层俩叶子，往上每层加一个叶子，叶子的权值下面小上面大。
详见百度百科-哈夫曼树
哈夫曼编码： 按照字符出现的概率分配哈夫曼树的叶子结点的权值，以实现平均码长最短的编码。每个字符的哈夫曼编码表示为：从根结点出发到目标结点，每走一个右子树加一个 111 ,否则加一个 000。
度： 节点的子节点数，特别的，称度为 000 的节点为叶子结点；树的度是其所有节点的度的最大值。
树的表示与储存： tree[i].child 存储着节点i的孩子的位置信息。tree[i].child.push_back(idx) 表示给节点i增加一个编号为 idx 的孩子.
完全二叉树: 若某二叉树深 kkk层，且除第 kkk 层外其他所有的层的结点总数达到最大值，同时第 kkk 层节点数小于等于 2k−12^{k-1}2k−1 并靠左侧连续，则称其为完全二叉树。即在完全二叉树中，编号为 iii 的结点与满二叉树中编号为 iii 的结点的位置相同。有 nnn 个结点的完全二叉树的深度为 ⌊log2n⌋+1\lfloor \log_2 n\rfloor +1⌊log2 n⌋+1 。
二叉搜索树： 也称为二叉查找树、二分搜索树、有序二叉树或排序二叉树，其满足以下几个条件：
1.1.1. 若任意结点的左子树不空，则其左子树上所有结点的值均不大于它的根结点的值。
2.2.2. 若任意结点的右子树不空，则其右子树上所有结点的值均不小于它的根结点的值。
对二叉搜索树进行删除、查找、插入的操作的平均时间复杂度为 O(logn)O(\log n)O(logn)，最坏为 O(n)O(n)O(n)。二叉搜索树的中序排列是一个有序序列。
AOVAOVAOV网：顶点表示活动，有向边表示活动之间的优先制约关系，(u,v)(u,v)(u,v) 表示活动 uuu 必须先于活动 vvv 进行，称这种有向图为顶点表示活动的网为 AOVAOVAOV 网。
拓扑排序-入度： 在有向图中，一个顶点 vvv 的入度指与该条边向关联的入边的条数。
拓扑排序-出度： 在有向图中，一个顶点 vvv 的入度指与该条边向关联的出边的条数。
拓扑排序： 拓扑排序解决的问题是给一个有向无环图的所有结点排序：每次去掉一个入度为 000 的顶点并更新所有与其有关系的顶点的入度。一个有向无环图的拓扑排序可能不唯一。
运算符重载
即在结构体内写sort函数的比较规则，下面是一个优先按照x降序排列的例子。
